"""
建立二叉树，前序，中序，后序遍历
根节点，左孩子，右孩子，辅助队列
判空
"""
class Node():
    def __init__(self, elem,lsub =None,rsub =None):
        self.elem = elem
        self.lsub = lsub
        self.rsub = rsub


class BioTree():
    def __init__(self):
        self.root = None
        self.assist_queue =[]

    def BuildTree(self,node:Node):
        if self.root == None:
            self.root = node
            self.assist_queue.append(node)
        else:
            self.assist_queue.append(node)
            if self.assist_queue[0].lsub is None:   #如果父节点左孩子空
                self.assist_queue[0].lsub = node    #node的值放入左孩子
            else:
                self.assist_queue[0].rsub = node    #node的值放入右孩子
                self.assist_queue.pop(0)            #都放入了，释放父节点

    def ProOrder(self,node:Node):     #前序
        if node:
            print(node.elem,end=' ')
            self.ProOrder(node.lsub)
            self.ProOrder(node.rsub)

    def MidOrder(self,node:Node):   #中序
        if node:
            self.MidOrder(node.lsub)
            print(node.elem,end=' ')
            self.MidOrder(node.rsub)


    def PoseOrder(self,node:Node):  #后序
        if node:
            self.PoseOrder(node.rsub)
            print(node.elem,end=' ')
            self.PoseOrder(node.lsub)
        # print()

    def LevelOrder(self):   #层序遍历，
        assist_queue = []
        assist_queue.append(self.root)    #根节点入队
        while assist_queue:    #先让第一个元素出队，打印出队元素。接着判断左孩子右孩子有没有，有的话，入队
            out_node:Node = assist_queue.pop(0)     #队中第一个元素出队
            print(out_node.elem,end=' ')
            if out_node.lsub:                       #如果左孩子不空，让左孩子入队
                assist_queue.append(out_node.lsub)
            if out_node.rsub:                       #如果右孩子不空，让右孩子入队
                assist_queue.append(out_node.rsub)


if __name__ == '__main__':
    tree = BioTree()
    node =Node
    for i in range(1,11):
        newNode = Node(i)
        tree.BuildTree(newNode)

    # tree.ProOrder(tree.root)
    # tree.MidOrder(tree.root)
    # tree.PoseOrder(tree.root)
    tree.LevelOrder()